/**
 *给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr 由 1 和若干 素数 组成，且其中所有整数互不相同。
 *
 * 对于每对满足 0 <= i < j < arr.length 的 i 和 j ，可以得到分数 arr[i] / arr[j] 。
 *
 * 那么第k个最小的分数是多少呢? 以长度为 2 的整数数组返回你的答案, 这里answer[0] == arr[i]且answer[1] == arr[j]
 *思路：构造容量为K的大根堆，然后如果下一个元素比堆顶元素小就交换，到最后堆顶元素就是第k小元素
 */
class KthSmallestPrimeFraction {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        PriorityQueue<int[]> maxHeap=new PriorityQueue<>(new Intcmp());
        int len=arr.length;
        for(int i=0;i<len;i++){
            for(int j=i+1;j<len;j++){
                int[] cur=new int[]{arr[i],arr[j]};
                if(maxHeap.size()<k){
                    maxHeap.offer(cur);
                }else{
                    if(isSmaller(cur,maxHeap.peek())){//如果下一个小于堆顶元素则，将堆顶元素与其替换，因为要保证外面的元素比堆里的元素大，这样堆顶元素就是第k小的元素
                        maxHeap.poll();
                        maxHeap.offer(cur);
                    }
                }
            }
        }
        return maxHeap.peek();
    }
    public boolean isSmaller(int[] cur,int[] pre){
        return cur[0]*pre[1]-cur[1]*pre[0]<0;
    }
}

class Intcmp implements Comparator<int[]>{

    @Override
    public int compare(int[] o1, int[] o2) {
        return o2[0]*o1[1]-o1[0]*o2[1];
    }
}
